/*
Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
*/

class Solution {
public:
    void do_permute(vector<int> &resone, vector<vector<int> > &res, vector<bool> &barray, vector<int> &num) {
        for (int i=0; i < num.size(); i++) {
            // pick next integer
            if (barray[i]) continue;
            resone.push_back(num[i]);
            barray[i] = true;
            if (resone.size() == num.size()) {
                res.push_back(resone);
            } else {
                do_permute(resone, res, barray, num);
            }
            // reset bit and pop back number
            resone.pop_back();
            barray[i] = false;
        }
    } 
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        if (!num.size()) return res;
        vector<bool> barray(num.size(), false);
        vector<int> resone;
        do_permute(resone, res, barray, num);
        return res;
    }
};
